package com.tgy.programmer_code_interview_guide._02_linkedList;

import com.tgy.leetcode.ListNode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/23/21 10:29 AM
 */
public class _05_链表部分翻转_recursion {

    public static ListNode reverseBetween(ListNode head, int m, int n) {


        if (head == null || head.next == null || n == m) {

            return head;
        }

        return reverse(head,m,n,1);
    }

    private static ListNode end = null;

    private static ListNode reverse(ListNode head,int m, int n, int index) {

        if (head == null || head.next == null || index >= n) {

            if (head != null && index >= n) {

                end = head.next;
            }

            return head;
        }


        if (index >= m && index < n) {

            ListNode nextNode = head.next;
            ListNode retNode = reverse(nextNode,m,n,index+1);
            nextNode.next = head;

            if (index == m) {

                head.next = end;
            }
            return retNode;
        }

        if (index == m - 1) {

           head.next = reverse(head.next,m,n,index+1);
        }else {

            reverse(head.next,m,n,index+1);
        }


        return head;
    }

    public static void main(String[] args) {

        ListNode root = ListNode.general(new int[]{1, 2, 3, 4, 5, 6});
        ListNode reverseRoot = reverseBetween(root,1,100);
        ListNode.printListNode(reverseRoot);
    }
}
